import java.util.Stack;
public class MySingleList {

    static class ListNode {
        public int val;//存储的数据
        public ListNode next;//存储下一个节点的地址，这是一个成员属性！！！next是一个成员属性！！！

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;// 代表当前链表的头节点的引用


    public void createLink() {
        //定义出链表的四个节点，但是此时只给val复制，next仍然为空
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(45);
        ListNode listNode3 = new ListNode(23);
        ListNode listNode4 = new ListNode(90);
        //这里给next赋值，存入下一个节点的地址
        listNode1.next = listNode2;//意为“将listNode2存放的地址给listNode1的next属性”
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        head = listNode1;
    }

    //递归打印链表
    public void display3(ListNode pHead) {
        if(pHead == null) {
            return;
        }
        if(pHead.next == null) {
            System.out.print(pHead.val+" ");
            return;
        }
        display3(pHead.next);
        System.out.print(pHead.val+" ");
    }

    public void display4() {
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //遍历栈
        while (!stack.isEmpty()) {
            ListNode top = stack.pop();
            System.out.print(top.val+" ");
        }
        System.out.println();
    }


    /**
     * 遍历链表
     */
    public void display() {
        //如果说 把整个链表 遍历完成 那么 就需要 head == null
        // 如果说 你遍历到链表的尾巴  head.next == null
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
/*    public void display() {
 //遍历链表，但是这样写会有什么问题呢？
// while (head.next != null) {//因为最后一个节点的next是null，所以这种方法少打印最后一个val
    while (head != null) {
        System.out.print(head.val+" ");
            head = head.next;
        }
        System.out.println();
    }*/
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //得到单链表的长度 O(N)
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //头插法 O(1)
    public void addFirst(int data){
        ListNode listNode = new ListNode(data);//获得一个节点
        listNode.next = head;//将原来的头节点的地址给新的头节点的next
        head = listNode;//将新节点设置为新的头节点
    }
    //尾插法 O(N)    找尾巴的过程
    public void addLast(int data){
        ListNode listNode = new ListNode(data);//获得一个节点
        if(head == null) {//当链表中没有节点时，插在末尾的这个节点就是第一个节点
            head = listNode;
            return;
        }
        ListNode cur = head;//当链表中有节点的时候，使用cur“代跑”来防止head头节点被改变
        while (cur.next != null) {//开始遍历链表，寻找最后一个节点
            cur = cur.next;
        }
        cur.next = listNode;//将新插在末尾的节点的地址给到原末尾节点的next
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data)throws ListIndexOutOfException{
        checkIndex(index);
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndexSubOne(index);//在index位置前插入，就是插在index这个位置上
        ListNode listNode = new ListNode(data);
        listNode.next = cur.next;
        cur.next = listNode;
    }

    private ListNode findIndexSubOne(int index) {//获取index前一个位置的下标 的 节点
        ListNode cur = head;
        int count = 0;
        while (count != index-1) {
            cur = cur.next;//将cur移到链表中的下一个节点处
            count++;
        }
        return cur;
    }
    private void checkIndex(int index) throws ListIndexOutOfException{//检查输入的节点下标是否合法
        if(index < 0 || index > size()) {
            throw new ListIndexOutOfException("index位置不合法");
        }
    }

    //删除第一次出现关键字为key的节点 O(N)
    public void remove(int key){
        if(head == null) {
            return ;//一个节点都没有
        }
        if(head.val == key) {//判断头节点是否是要删除的节点
            head = head.next;
            return;
        }
        ListNode cur = searchPrev(key);//找到key的前一个节点
        if(cur == null) {//没有要删除的节点
            return;
        }
        ListNode del = cur.next;//要删除的节点del
        cur.next = del.next;//跳过该地址实现删除
    }

    private ListNode searchPrev(int key) {//找到key的前一个节点（head不为空，所以要加判断条件）
        if (head == null){//一个节点都没有
            return null;
        }
        ListNode cur = head;
        while (cur.next != null) {//只要不是最后一个节点，就有可能是要删除对象的前一个节点
            if(cur.next.val == key) {//如果找到了key的前一个节点就返回cur
                return cur;
            }
            cur = cur.next;//没找到就接着往后找
        }
        return null;//没有你要删除的节点
    }

    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head == null) {
            return;
        }
        /*while(head.val == key) {
            head = head.next;
        }*/
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == key) {//判断第一个节点是否为目标节点
            head = head.next;
        }
    }

    /**
     * 保证链表当中 所有的节点 都可以被回收
     */
    public void clear() {
        head = null;

        //StringBuilder sb = "fdfa";
    }
}






